#include<iostream>
#include<vector>
#include<time.h>
using std::cout;
using std::endl;

#ifdef _WIN32
	#include<windows.h>
#else
//
#endif

// 定长内存池
//template<size_t N>
//class ObjectPool
//{};

// 直接去堆上按页申请空间
//直接从操作系统申请大块内存（按 “页” 为单位），比malloc更底层，减少中间开销。
inline static void* SystemAlloc(size_t kpage)
{	
#ifdef _WIN32 
//Windows 用 VirtualAlloc（系统 API），直接向系统申请虚拟内存
	void* ptr = VirtualAlloc(0, kpage<<13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
	#include <sys/mman.h>
    #include <unistd.h>
    void* ptr = mmap(nullptr, kpage << 13, PROT_READ | PROT_WRITE, 
                     MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
    if (ptr == MAP_FAILED) {
        ptr = nullptr;
    }
#endif
	if(ptr == nullptr)
		throw std::bad_alloc();//内存分配失败的异常

	return ptr;
}

template<class T>
class ObjectPool
{
public:
	T* New()
	{
		T* obj = nullptr;

		// 优先把还回来内存块对象，再次重复利用
		if(_freeList)
		{
		// 第一步：从当前“二手对象”里，取出“下一个二手对象”的地址	
		// 因为 _freeList 存的是对象指针，而对象里藏着下一个节点的地址（链表结构）
    	// 这里强制转成 void** ，就是为了拿到“下一个节点的地址”
		//void**还有一个好处，无论32/64位，都能完美适配，因为void*是指针，大小不确定
			void* next = *((void**)_freeList);

		// 第二步：把当前“二手对象”取出来，给用户用	
			obj = (T*)_freeList;

		// 第三步：“二手仓库”的链表头，移动到下一个节点
    	// 这样下次再取，就从下一个“二手对象”开始	
			_freeList = next;
		}
		else
		{
			// 剩余内存不够一个对象大小时，则重新开大块空间(拿一个新箱子)
			if(_remainBytes < sizeof(T))
			{
				_remainBytes = 128 * 1024;
				//_memory = (char*)malloc(_remainBytes);
				_memory = (char*)SystemAlloc(_remainBytes >> 13);
				if(_memory == nullptr)
				{
					throw std::bad_alloc();
				}
			}

			// 从箱子最前面拿一块空间当对象
			obj = (T*)_memory;
			//如果T很小（比如char只有 1 字节），也得按指针大小（通常 8 字节）分配
			//因为将来这个对象不用了，要放进 二手仓库（链表），需要额外空间存下一个对象的地址
			//再直白解释哪怕顾客只买个小玩意（小T），包装也得留够贴标签的地方（指针大小），方便将来回收再卖
			size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);

			_memory += objSize;  // 箱子指针往后挪，跳过刚拿走的部分
			_remainBytes -= objSize;  // 剩余空间减少
		}	

		// 定位new，显示调用T的构造函数初始化 --- why？
		//new会自动做两件事：分配内存 + 调用构造函数
		//这里内存已经提前分配好了，缺 “初始化对象” ，所以必须显式调用构造函数
		new(obj)T;

		return obj;
	}

	void Delete(T* obj)
	{
		// 显示调用析构函数清理对象
		obj->~T();

		//头插法：把当前对象插到链表最前面
		*(void**)obj = _freeList;// 让当前对象“记住”仓库里原来的第一个对象
		_freeList = obj;// 仓库的入口换成当前对象
		//*理解：每个节点的解引用是下一个节点
	}

private:
	char* _memory = nullptr;//指向当前未分配的大块内存的起始地址
	size_t _remainBytes = 0;//当前大块内存中剩余的可分配字节数
	
	//_freeList 想象成一个“二手对象链表”，里面存的是之前 Delete 回收的对象
	//（别人用完不要的，但还能接着用）链表的每个节点就是一个 “二手对象”，
	//节点里还藏着 “下一个二手对象在哪” 的信息
	void* _freeList = nullptr;//还回来过程中链接的自由链表的头指针
};

struct TreeNode
{
	int _val;
	TreeNode* left;
	TreeNode* right;

	TreeNode()
		:_val(0)
		,left(nullptr)
		,right(nullptr)
	{}
};

//性能测试函数
void TestObjectPool()
{
	const size_t Rounds = 5;// 测试轮次：重复5轮，让结果更可信
	const size_t N = 100000;// 每轮次数：每次创建/销毁10万个对象（TreeNode）

	//1. 测试普通的new/delete
	std::vector<TreeNode*> v1;// 存创建的对象指针
	v1.reserve(N);	// 提前开好vector空间，避免干扰测试

	size_t begin1 = clock(); //记录开始时间
	// 重复Round轮
	for(size_t j = 0; j < Rounds; j++)
	{
		// 1.创建N个对象（用new）
		for(int i = 0; i < N; i++)
		{
			v1.push_back(new TreeNode);//向系统申请新内存
		}
		// 2.销毁N个对象（用delete）
		for(int i = 0; i < N; i++)
		{
			delete v1[i];//向系统释放内存
		}
		v1.clear();  // 清空vector，准备下一轮
	}
	size_t end1 = clock();  // 记录结束时间

	std::vector<TreeNode*> v2;
	v2.reserve(N);

	ObjectPool<TreeNode> TNPool;// 创建TreeNode类型的对象池
	size_t begin2 = clock();
	for (size_t j = 0; j < Rounds; ++j)
	{
    	// 第1步：从对象池拿N个对象（New()）
    	for (int i = 0; i < N; ++i)
    	{
        	v2.push_back(TNPool.New());  // 优先复用旧对象，不够再切新内存
    	}
    	// 第2步：把N个对象放回池（Delete()）
    	for (int i = 0; i < N; ++i)
    	{
        	TNPool.Delete(v2[i]);  // 不释放内存，只是放回自由链表
    	}
    	v2.clear();
	}
	size_t end2 = clock();

	cout << "new cost time:" << end1 - begin1 << endl;
	cout << "object pool cost time:" << end2 - begin2 << endl;
}